import java.util.*;

public class code3 {
    boolean[] vis = new boolean[15];//标记当前位置是否使用过
    StringBuffer path = new StringBuffer();
    ArrayList<String> ret = new ArrayList<>();//收集叶子结点
    char[] s;
    int n;

    public ArrayList<String> Permutation (String str) {
        n = str.length();
        s = str.toCharArray();
        Arrays.sort(s);

        dfs(0);
        return ret;
    }
    public void dfs(int pos) {
        if(pos==n) {
            ret.add(path.toString());
            return;
        }

        //填pos位置
        for(int i=0;i<n;i++) {
            if(vis[i]) continue;
            if(i>0&&s[i]==s[i-1]&&!vis[i-1]) continue;
            path.append(s[i]);
            vis[i]=true;
            dfs(pos+1);
            //恢复现场
            vis[i] = false;
            path.deleteCharAt(path.length()-1);
        }

    }
}